package org.aplombh.java.awcing.basic.basics.sort.quickSort;

import org.regotto.common.Utils;

/**
 * quickSort algorithm
 */
public class MyQuickSort {
    /**
     * quick sort algorithm 快速排序算法
     *
     * @param ints  unsorted array 待排序算法
     * @param left  left margin 左边界
     * @param right right margin 有边界
     */
    public static void quickSort(int[] ints, int left, int right) {

        // If the function reaches the boundary, the recursion exits
        // 如果方法到达边界，退出递归
        if (left >= right) return;


        // x is the cut-off point index, generally, There are the following methods to get the value
        //  -- 1.take the median          -> index = left + right >> 1
        //  -- 2.take the left endpoint   -> index = right
        //  -- 3.take the right endpoint  -> index = left
        //  -- 4.take the random index    -> index = DataUtils.getInt(left, right)
        // x是分界点下标，通常来说有以下几种方法获得
        // -- 1、获取中间点          -> index = left + right >> 1
        // -- 2、获取左端点          -> index = right
        // -- 3、获取右端点          -> index = left
        // -- 4、获取随机下标        -> index = DataUtils.getInt(left, right)
        int x = ints[left + right >> 1], i = left - 1, j = right + 1;

        // Move all numbers less than x to the left of the array
        // Move all numbers more than x to the right of the array
        // 移动所有小于x的数到数组的左边
        // 移动所有大于x的数到数组的右边
        while (i < j) {

            // swap ints[i] and ints[j] when ints[i] is greater than x and ints[j] is less than x
            // 找到ints[i] < x 并且 ints[j] > x 的位置交换两位置的值
            while (ints[++i] < x) ;
            while (ints[--j] > x) ;
            if (i < j) Utils.swap(ints, i, j);
        }

        // Quick sort left partition and right partition;
        // 对左右两边分别进行快速排序
        quickSort(ints, left, j);
        quickSort(ints, j + 1, right);
    }
}
